# 全排列2-无重复排列


def dfs(nums, depth, res, path, used):
    if (depth == len(nums)):
        res.append(path.copy())
        return
    for i in range(len(nums)):
        if not used[i]:
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            path.append(nums[i])
            used[i] = True
            dfs(nums, depth + 1, res, path, used)
            # 回溯
            used[i] = False
            path.pop()




class Solution:

    def permuteUnique(self, nums):
        used = []
        depth = 0
        res = []
        path = []
        for _ in range(len(nums)):
            used.append(False)
        if len(nums) == 0:
            return res
        # 这一步非常重要
        nums.sort()
        dfs(nums, 0, res, path, used)
        return res

# print(Solution.permuteUnique(self=None, nums = [3, 3, 0, 3]))